/**
 * 面试题63：股票的最大利润
 */
public class Offer_63 {
    /**
     * 方法二：一次遍历
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 初始化最大利润为0，股票最低价为第一天
        int maxProfit = 0, minPrice = prices[0];
        for (int i = 1; i < len; i++) {
            // 更新股票最低价
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
            // 更新最大利润
            if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }

    /**
     * 方法一：暴力法
     * <p>
     * 时间复杂度：O(n^2)
     * <p>
     * 空间复杂度：O(1)
     */
    public int maxProfit1(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        int maxProfit = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }
}
